﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using Graph;
using Graph.Interfaces;
using GraphTraversal.Interfaces;

namespace GraphTraversal
{
    public class Traversal : ITraversal
    {
        private IBasicGraph _graph;



        public Traversal()
        {
            _graph = new BasicGraph();
        }

        /// <summary>
        /// Traverses a graph beginning at vertex by
        /// using a depth-first search: Iterative version
        /// </summary>
        public IList DfsIterative(Vertex vertex)
        {
            List<Vertex> result = new List<Vertex>();
            Stack<Vertex> s = new Stack<Vertex>();
            result.Add(vertex);
            s.Push(vertex);
            vertex.Marked = true;

            while (s.Count > 0)
            {
                Vertex v = _graph.GetNextUnmarked((List<Vertex>)_graph.GetAdjacencies(s.Peek()));
                if (v == null) // no unvisited vertices adjacent
                {
                    s.Pop(); // backtrack
                }
                else
                {
                    result.Add(v);
                    s.Push(v);
                    v.Marked = true;
                } // end if else
            } // end while
            _graph.UnMark();
            return result;
        }

        List<Vertex> dfsrResult = new List<Vertex>();
        /// <summary>
        /// Traverses a graph beginning at vertex by
        /// using a depth-first search: Recursive version
        /// </summary>
        public IList DfsRecursive(Vertex vertex)
        {
            try
            {
                vertex.Marked = true;
                dfsrResult.Add(vertex);

                foreach (Vertex v in _graph.GetAdjacencies(vertex))
                {
                    if (!v.Marked) // else backtrack
                    {
                        DfsRecursive(v);
                    } // end if
                }// end foreach

                return dfsrResult;
            }
            finally
            {
               _graph.UnMark();
            }
        }

        /// <summary>
        /// Traverses a graph beginning at vertex by
        /// using a breadth-first search: Iterative version
        /// </summary>
        public IList BfsIterative(Vertex vertex)
        {
            List<Vertex> result = new List<Vertex>();
            Queue<Vertex> q = new Queue<Vertex>();
            result.Add(vertex);
            q.Enqueue(vertex);
            vertex.Marked = true;

            while (q.Count > 0)
            {
                foreach (Vertex v in _graph.GetAdjacencies(q.Dequeue()))
                {
                    if (!v.Marked)
                    {
                        result.Add(v);
                        q.Enqueue(v);
                    }
                }
            }
            _graph.UnMark();
            return result;
        }
    }
}
